
public class Kadane {

	 public int maxSubArray(int[] A) {
	      int max=A[0];
	      int last=max;
	      
	      for(int i=1;i<A.length;i++){
	    	  if(max<=0){
	    		  max=A[i];
	    	  }else{
	    		  max+=A[i];
	    		  if(max>last)
	    			  last=max;
	    	  }
	      }
	      return max>last?max:last;
	 }
}